package algorithm.tic_tac_toe;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;

import library.Tracer;

public class MiniMax {
	private ChessBoard chessBoard;
	private Point computerMovePoint;

	private Point scanInput() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("row,col = ");
		Point p = new Point();
		try {
			String line = br.readLine();
			String[] coordinate = line.split("[, \\.]");
			p.y = Integer.parseInt(coordinate[0]) - 1;
			p.x = Integer.parseInt(coordinate[1]) - 1;
		} catch (Exception e) {
		}
		return p;
	}

	public void run() {
		Point p;
		int ret;
		Tracer.splitLine("begin");
		for (;;) {
			do {
				Tracer.splitLine("human turn");
				chessBoard.disp();
				// human moving
				p = scanInput();
			} while (!chessBoard.setChessHuman(p.x, p.y));

			// computer moving
			ret = evaluateComputerMove(chessBoard, 0, ChessBoard.MIN_INFINITY, ChessBoard.MAX_INFINITY);

			p = computerMovePoint;
			if (!chessBoard.setChessComputer(p.x, p.y))
				break;

			chessBoard.disp();
			if (ret == ChessBoard.MIN_INFINITY) {
				System.out.println("human win");
				break;
			} else if (ret == ChessBoard.MAX_INFINITY) {
				System.out.println("computer win");
				break;
			}
		}
		Tracer.splitLine("over");
		chessBoard.disp();
	}

	/**
	 * select Maximum value from Minimum values of subchessboard
	 * 
	 * @param cb
	 * @return
	 */
	public int evaluateComputerMove(ChessBoard cb, int depth, int alpha, int beta) {
		int i, j, value;
		int max = ChessBoard.MIN_INFINITY - 1;

		/* The human (min) just made a move, so we evalue that move here */
		if (cb.checkPlayerWin(ChessBoard.HUMAN))
			return ChessBoard.MIN_INFINITY;

		for (i = 0; i < ChessBoard.N; i++) {
			for (j = 0; j < ChessBoard.N; j++) {
				ChessBoard cb_tmp = cb.deepCopy();
				if (!cb_tmp.setChessComputer(j, i))
					continue;

				value = evaluateHumanMove(cb_tmp, depth + 1, alpha, beta);

				if (value > max) {
					max = value;
					if (depth == 0) {
						computerMovePoint.x = j;
						computerMovePoint.y = i;
					}
				}
				/*
				 * alpha defines the best scheme that realize the maximization
				 * goal
				 */
				if (value > alpha)
					alpha = value;
				/* Prune this subtree by not checking any further successors */
				if (alpha >= beta)
					return alpha;// return breaks the loop, cuts
									// subTrees
			}
		}

		/* No move is possible -- draw */
		if (max == ChessBoard.MIN_INFINITY - 1)
			return ChessBoard.DRAW;
		return max;
	}

	/**
	 * select Minimum value from Maximum values of subchessboard
	 * 
	 * @param cb
	 * @return
	 */
	public int evaluateHumanMove(ChessBoard cb, int depth, int alpha, int beta) {
		int i, j, value;
		int min = ChessBoard.MAX_INFINITY + 1;

		/* the computer (max) just made a move, so we evaluate that move here */

		if (cb.checkPlayerWin(ChessBoard.COMPUTER))
			return ChessBoard.MAX_INFINITY;

		for (i = 0; i < ChessBoard.N; i++) {
			for (j = 0; j < ChessBoard.N; j++) {
				ChessBoard cb_tmp = cb.deepCopy();
				if (!cb_tmp.setChessHuman(j, i))
					continue;

				value = evaluateComputerMove(cb_tmp, depth + 1, alpha, beta);

				if (value < min)
					min = value;

				if (value < beta)
					beta = value;
				/* Prune this subtree by not checking any further successors */
				if (alpha >= beta)
					return beta;
			}
		}

		/* No move is possible -- draw */
		if (min == ChessBoard.MAX_INFINITY + 1)
			return ChessBoard.DRAW;
		return min;
	}

	public MiniMax() {
		chessBoard = new ChessBoard();
		computerMovePoint = new Point();
	}
}

//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
